;; 组合数学第四章 GENERATING PERMUTATIONS AND COMBINATIONS
;;
;; 产生所有的排列
(load "../sicp/base.scm")
;; fun(left-part right-part)
(define (map-left-right fun sequence)
  (define (iter left right result)
    (if (null? right)
	(append result (list (fun left right)))
	(iter (append left (list (car right)))
	      (cdr right)
	      (append result  (list (fun left right))))))
  (iter '() sequence '()))
;; (map-left-right (lambda (left right) left) '(1 2 3))
(define (gen-permutations-recursive items)
  (define (combine x perm)
    (map-left-right (lambda (left right) (append left (list x) right))
		    perm))
  (cond ((null? items) '())
	((= 1 (length items)) (list items))
	(else (accumulate append
		  '() 
		  (map (lambda (perm) (combine (car items) perm))
		       (gen-permutations (cdr items)))))))
;; (length (gen-permutations (enumerate-interval 1 10)))
(define (gen-permutations-use-mobile n)
  (define left 0)
  (define right 1)
  (define (kth-item k items) (list-ref items k))
  (define (index-of item items) (- (length items)
				   (length (member item items))))
  (define (first? item items) (= 0 (index-of item items)))
  (define (last? item items) (= (- (length items) 1)
				(index-of item items)))
  (define (pre-item item items)
    (if (first? item items) 
	'()
	(kth-item (- (index-of item items) 1) items)))
  (define (next-item item items)
    (if (last? item items) 
	'()
	(kth-item (+ (index-of item items) 1) items)))
  (define (num item) (car item))
  (define (direction item) (cdr item))
  (define (mobile? item items) 
    (if (= left (direction item))
	(if (first? item items) 
	    #f 
	    (> (num item) (num (pre-item item items))))
	(if (last? item items)
	    #f 
	    (> (num item) (num (next-item item items))))))
  (define (find-largest-mobile items)
    (let ((max-mobile (accumulate 
		       (lambda (x y) (if (mobile? x items)
					 (max (num x) y)
					 y))
		       -1 items)))
      (if (= -1 max-mobile) #f (assq max-mobile items))))
  (define (iter items result)
    (let* ((max-mobile (find-largest-mobile items))
	   (m (if max-mobile (num max-mobile) '())))
      (if (not max-mobile)
	  (cons (map num items) result)
	  (let ((dir-item (if (= left (direction max-mobile))
			     (pre-item max-mobile items)
			     (next-item max-mobile items))))
	    (iter (map (lambda (x)
			 (cond ((> (num x) m) 
				(cons (num x)
				      (if (= left (direction x)) right left)))
			       ((equal? max-mobile x) dir-item)
			       ((equal? dir-item x) max-mobile)
			       (else x)))
		       items)
		(cons (map num items) result))))))
  (reverse (iter (map (lambda (x) (cons x left)) (enumerate-interval 1 n)) '())))
(gen-permutations-use-mobile 4)
;; (define items  (map (lambda (x) (cons x left)) (enumerate-interval 1 n)))
;; (assq 1 items)
;; (find-largest-mobile items)
;; (define item (cons 1 0))
;; (mobile? item items)
;; (pre-item item items)
;; (define n 5)
;; (define tf #f)
;; (if tf 't 'f)
;; 
;; (eq? '(1 2) '(1 2))     
;; (eqv? '(1 2) '(1 2))
;; (equal? '(1 2) '(1 2))
;; (list-ref '(1) 0)
;; (max 1 2)
;; (member '(1 1) '((3 3) (1 1) (2 2)))
;; (member '(2 2) '((3 3) (1 1) (2 2)))
;; (next-item '(2 2) '((3 3) (1 1) (2 2)))
;; (define x 5)
;; (define perm '(1 2 3 4))
;; (define items '(1 2 3 4))
;; (define v (make-vector 10 0))
;; (map (lambda (x) (+ 1 x)) (vector->list v))
;; (define (vector-set-test-1 v) (vector-set! v 0 1))
(define (fill-inverse-2! n i v)
  (do ((k 0 (+ 1 k))
       (i i (if (= 0 (vector-ref v k)) (- i 1) i)))
      ((and (= i 0) (= 0 (vector-ref v k))) (vector-set! v k n) v)))
;; (fill-inverse-2! 1 0 (make-vector 10 0))
;; (fill-inverse-2! 1 2 (make-vector 10 0))
;; (fill-inverse-2! 1 9 (make-vector 10 0))
;; (fill-inverse-2! 1 5 (make-vector 8 0))
(define (inverse->permutation-2 inverse)
  (let* ((n (vector-length inverse))
       (perm (make-vector n 0)))
    (do ((k 0 (+ 1 k)))
	((= k n) perm)
      (fill-inverse-2! (+ 1 k) (vector-ref inverse k) perm))))
;; (inverse->permutation-2 '#(5 3 4 0 2 1 1 0))
;; (define inverse '#(5 3 4 0 2 1 1 0))
;; (define v (make-vector 8 0))
;; (fill-inverse-2! 1 5 v)
;; (fill-inverse-2! 2 3 v)
;; (fill-inverse-2! 3 4 v)
;; (fill-inverse-2! 4 0 v)
;; (do ((v (make-vector 10 0))
;;      (i 0 (+ i 1))
;;      (j (+ i 1)))    
;;     ((= 10 i) v)
;;   (vector-set! v i j))
(define (list-insert! lst i item)
  (define (iter lst i)
    (if (zero? i)
	(cons item lst)
	(cons (car lst) (iter (cdr lst) (- i 1)))))
  (iter lst i))
;; (list-insert! '() 0 1)
;; (list-insert! '(1 2 3) 1 5)
(define (gen-inverse n)
  (if (= 1 n)
      (list (list 0))
      (flatmap (lambda (inverse) (map (lambda (x) (cons x inverse))
				      (enumerate-interval 0 (- n 1))))
	       (gen-inverse (- n 1)))))
;; (gen-inverse 3)
(define (gen-permutations-algorithm-2 n)
  (map (lambda (inverse)
	 (vector->list (inverse->permutation-2 (list->vector inverse))))
       (gen-inverse n)))
;; (gen-permutations-algorithm-2 3)


